Specialized transduction has proven to be useful for generating deletion mutants in most mycobacteria, including virulent Mycobacterium tuberculosis. We have improved this system by developing (i) a single-step strategy for the construction of allelic exchange substrates (AES), (ii) a temperature-sensitive shuttle phasmid with a greater cloning capacity than phAE87, and (iii) bacteriophage-mediated transient expression of site-specific recombinase to precisely excise antibiotic markers. The methods ameliorate rate-limiting steps in strain construction in these difficult-to-manipulate bacteria. The new methods for strain construction were demonstrated to generalize to all classes of genes and chromosomal loci by generating more than 100 targeted single- or multiple-deletion substitutions. These improved methods pave the way for the generation of a complete ordered library of M. tuberculosis null strains, where each strain is deleted for a single defined open reading frame in M. tuberculosis.